package demo1;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //全队列 2
    HashSet<List<Integer>> hs = new HashSet<>();
    int[] nums;
    boolean[] visited;

    public List<List<Integer>> permuteUnique(int[] nums) {
        this.nums = nums;
        visited = new boolean[nums.length];
        dfs(new ArrayList<>());
        return hs.stream().toList();
    }

    public void dfs(List<Integer> list) {
        if(list.size() == nums.length){
            hs.add(new ArrayList<>(list));
        }
        for(int i = 0; i < nums.length; i++){
            if(!visited[i]){
                visited[i] = true;
                list.add(nums[i]);
                dfs(list);
                visited[i] = false;
                list.removeLast();
            }
        }
    }

    //反转偶数长度组的节点
    public ListNode reverseEvenLengthGroups(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy, end = dummy;
        int cnt = 1;
        while (end.next != null) {
            int n = 0;
            for (int i = 0; i < cnt && end.next != null; i++) {
                end = end.next;
                n++;
            }
            if (end == null)
                break;
            if (n % 2 == 0) {
                ListNode start = pre.next;
                ListNode next = end.next;
                end.next = null;
                pre.next = reverse(start);
                start.next = next;
                pre = start;
                end = pre;
            } else {
                pre = end;
            }
            cnt++;
        }
        return dummy.next;
    }

    ListNode reverse(ListNode node) {
        ListNode pre = null;
        ListNode cur = node;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
